# include "MathFunc.h"

using namespace std;

namespace MathFunction
{
	Prime::Prime(int upperBound)
	{
		if (upperBound < 0)
		{
			throw std::exception("Non-negative integer required.");
		}

		upperBound ++;
		_upperBound = upperBound;

		// Construct a vector with total amount of upperBound size
		std::vector<int> notPrime(upperBound, 0);
		
		for (int i = 2; i < upperBound; i ++)
		{
			// If current number is a prime, push it back to the primeList.
			if (notPrime[i] == 0)
			{
				primeList.push_back(i);
			}
		
			int totalPrime = (int)primeList.size();
			
			// We do a prime sieve here using the current number and the primes
			// in the primeList. It's obvious that a prime * current number
			// will produce a compound, so we use the primes to mark out all
			// the compounds. It can be proved that this method only requires
			// O(N), N is the upper bound of the sieve.
			for (int j = 0; j < totalPrime && 
							primeList[j] * primeList[j] < upperBound; j ++)
			{
				if (primeList[j] * i < upperBound)
				{
					notPrime[primeList[j] * i] = true;
				}
				
				// This line is to ensure an O(N) implementation. If current
				// number is already a compound, say k * primeList[j], then
				// i * primeList[j + 1] will be marked as compound when we are
				// checking k * primeList[j + 1]. Therefore in current round,
				// we save time by not overdo something that will be done in
				// the future round.
				if (i % primeList[j] == 0) break;
			}
		}
	}

	vector<int> Prime::GetPrimeList()
	{
		return primeList;
	}

	vector<int> Prime::FindPrimeLessThan(int bound)
	{
		vector<int> temp;

		if (bound < 0)
		{
			throw std::exception("Non-negative integer required.");
		}
		
		int index = lower_bound(primeList.begin(),
								primeList.end(), bound) - primeList.begin();

		// There will be chances the bound itself is a prime.
		if (primeList[index] == bound) index ++;

		for (int i = 0; i < index; i ++)
		{
			temp.push_back(primeList[i]);
		}

		return temp;
	}
}